package Graph;

import java.util.Arrays;

/**
 * @ClassName Graph.UnionFindSet
 * @Description TODO
 * @Author MOSS
 * @Date 2023/12/30 18:48
 * @Version 1.0
 */
public class UnionFindSet {
    private int []  nums;
    private int count = 0;
    public UnionFindSet(int size){
        nums = new int[size];
        Arrays.fill(nums,-1);
    }
    public int findRoot(int index){
      while(nums[index] >= 0 ){
          index = nums[index];
      }
      return index;
    }
    // index2 加入到 index1 中
    public void union(int index1, int index2){
        if(findRoot(index1) == findRoot(index2)){
            return;
        }
        int root_index1 = findRoot(index1);
        int root_index2 = findRoot(index2);
        nums[root_index1] = nums[root_index1] + nums[root_index2];
        nums[root_index2] = index1;
    }
    public boolean isInSameSet(int srcIndex, int destIndex){
        return findRoot(srcIndex) != findRoot(destIndex);
    }
    public int getCount(){
        for(int x: nums){
            if(x < 0){
                count++;
            }
        }
        return count;
    }
    public void print(){
        for(int x : nums){
            System.out.print(x+" ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        UnionFindSet unionFindSet = new UnionFindSet(10);
        System.out.println("0 和 3是亲戚");


        unionFindSet.union(0,3);
        unionFindSet.print();

        System.out.println("0 和 2是亲戚");
        unionFindSet.union(0,2);
        unionFindSet.print();
        System.out.println("2 和 4是亲戚");
        unionFindSet.union(2,4);
        unionFindSet.print();

        //unionFindSet.print();
    }
}
